package me.mingshan.sort;

import java.util.Arrays;

/**
 * @author hanjuntao
 * @date 2025/2/24 0024
 */
public class Test2 {
    public static void main(String[] args) {
//        int[] source = {4, 3, 8, 2, 1, 5, 7, 4, 5};
//
//        int[] source2 = {4, 5, 6, 3};
//
//        quickSort(source2, 0, source2.length - 1);
//        System.out.println(Arrays.toString(source2));

                int[] source3 = {2,2};
//
        int[] source4 = {2,2};
        int[] merge = merge(source3, source4);
        System.out.println(Arrays.toString(merge));
    }

    private static void sort(int[] source) {
        if (source == null) {
            return;
        }

        // 3 4 2 1
        // 3 4 2 1
        // 2 4 3 1
        // 2 3 1 3

        for (int i = 0; i < source.length; i++) {
            for (int j = 0; j < source.length - i - 1; j++) {
                if (source[j] > source[j + 1]) {
                   int temp = source[j];
                   source[j] = source[j + 1];
                   source[j + 1] = temp;
                }
            }
        }
    }

    private static void insertSort(int[] source) {
        if (source == null) {
            return;
        }

        // 3 4 2 1
        // 3 2 4 1

        for (int i = 1; i < source.length; i++) {
            for (int j = i; j > 0; j--) {
                // 如果前面的大于后面的，交换顺序
                if (source[j - 1] > source[j]) {
                    int temp = source[j];
                    source[j] = source[j - 1];
                    source[j - 1] = temp;
                }
            }
        }
    }

    private static void quickSort(int[] source, int low, int high) {
        if (source == null) {
            return;
        }

        if (low >= high) {
            return;
        }

        int i = low;
        int j = high;

        int pivotIndex = low;
        int pivotValue = source[pivotIndex];

        while (i != j) {
            // j 先从右往左走，找到第一个小于基准的数
            while (i < j) {
                if (source[j] < pivotValue) {
                    break;
                }
                j--;
            }

            // i 从左往右走，找到第一个大于基准的数
            while (i < j) {
                if (source[i] > pivotValue) {
                    break;
                }
                i++;
            }

            // 两者交换数据
            if (i < j) {
                int temp = source[i];
                source[i] = source[j];
                source[j] = temp;
            }
        }

        // 当两者相遇时，左边的，都小于基准，右边的，都大于基准
        // 将当前的位置数据与原基准交换位置
        if (source[i] < pivotValue) {
            int temp = source[pivotIndex];
            source[pivotIndex] = source[i];
            source[i] = temp;
        }

        // 基于当前基准两边的数据进行递归
        quickSort(source, low, i - 1);
        quickSort(source, i + 1, high);
    }




    private static int[] merge(int[] arr1, int[] arr2) {
        int[] temp = new int[arr1.length + arr2.length];

        // 双指针，同时指向两个数组
        int i = 0;
        int j = 0;

        // 下一个可用的下标
        int idx = 0;

        // 循环比较，将较小的数放入temp
        while (i < arr1.length && j < arr2.length)  {
            if (arr1[i] < arr2[j]) {
                temp[idx] = arr1[i];
                i++;
                idx++;
            } else if (arr1[i] > arr2[j]) {
                temp[idx] = arr2[j];
                j++;
                idx++;
            } else {
                temp[idx] = arr1[i];
                temp[idx+1] = arr2[j];

                i++;
                j++;
                idx = idx + 2;
            }
        }

        // 将剩余的元素拷贝到temp
        if (i <= arr1.length - 1) {
           for (int k = i; k < arr1.length; k++) {
               temp[idx] = arr1[k];
               idx++;
           }
        }

        if (j <= arr2.length - 1) {
           for (int k = j; k < arr2.length; k++) {
               temp[idx] = arr2[k];
               idx++;
           }
        }

        return temp;
    }
}
